package haff;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class Haff {
	private HashMap<String, String> code = new HashMap<>();
	private Node root;
	private int mod;

	public Haff() {
		// TODO Auto-generated constructor stub
	}

	public String load(String path, boolean isBinary) {
		StringBuilder text = new StringBuilder();
		byte[] array = new byte[1];
		try (InputStream in = Files.newInputStream(Paths.get(path))) {
			System.out.println(in.available());
			while (in.available() > 1) {
				in.read(array);
				text.append(isBinary ? decompress(array) : (char) array[0]);
			}
			text.append(isBinary?decompress(array).substring(mod):(char)array[0]);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return text.toString();
	}

	private String decompress(byte[] bits) {
		BitSet bit_Set = BitSet.valueOf(bits);
		String str = "";
		for (int i = 7; i > -1; --i) {
			str += bit_Set.get(i) ? "1" : "0";
		}
		return str;
	}

	/**
	 * 通过haff树解码 8ms
	 * 
	 * @param text
	 * @param root
	 * @return
	 */
	public String decodeByHaffTree(String text, Node root) {
		// Long start=System.currentTimeMillis();
		StringBuilder str = new StringBuilder();
		Node node = root;
		for (int i = 0; i < text.length(); i++) {
			if (text.charAt(i) == '0') {
				node = node.left;
			}
			if (text.charAt(i) == '1') {
				node = node.right;
			}
			if (node.left == null && node.right == null) {
				str.append(node.value);
				node = root;
			}
		}
		// Long end=System.currentTimeMillis();
		// System.out.println("消耗时间："+(end-start)+"ms");
		return str.toString();
	}

	/**
	 * 使用默认密码表进行解码
	 * 
	 * @param text
	 * @return
	 */
	public String decodeByCodeMap(String text) {
		return decodeByHaffTree(text, this.root);
	}

	/**
	 * 提供密码表进行解码
	 * 
	 * @param text
	 * @param codeMap
	 * @return
	 */
	public String decodeByCodeMap(String text, HashMap<String, String> codeMap) {
		if (codeMap.size() == 0) {
			return null;
		}

		StringBuilder str = new StringBuilder();
		int size = text.length();
		for (int i = 0; i < size; ++i) {
			for (int j = i + 1; j < size + 1; ++j) {
				String temp = text.substring(i, j);

				if (codeMap.containsValue(temp)) {

					codeMap.entrySet().stream().filter(x -> x.getValue().equals(temp)).map(x -> x.getKey())
							.forEach(str::append);
					i = j - 1;
					break;
				}
			}
		}

		return str.toString();
	}

	/**
	 * 计算字符频数
	 * 
	 * @param text
	 * @return
	 */
	public HashMap<String, Integer> count(String text) {
		HashMap<String, Integer> countMap = new HashMap<>();
		int size = text.length();

		for (int i = 0; i < size; ++i) {
			String key = text.substring(i, i + 1);
			if (countMap.containsKey(key)) {
				countMap.put(key, countMap.get(key) + 1);
			} else {
				countMap.put(String.valueOf(key), 1);
			}
		}

		return countMap;
	}

	/**
	 * 编码
	 * 
	 * @param text
	 */
	public void encode(String text, String path) {
		root = encode_(text);
		String haffText=encodeText(text);
		saveToFile(haffText.getBytes(), path);
		compress(haffText,"D:\\ff.huf");
	}

	/**
	 * 
	 * @param text
	 * @return
	 */
	private Node encode_(String text) {
		HashMap<String, Integer> map = count(text);
		ArrayList<Node> list = new ArrayList<>();
		map.entrySet().stream().forEach(x -> list.add(new Node(x.getKey(), x.getValue(), true)));

		Node root = haff(list);
		if (root.getIs())
			code.put(root.getValue(), root.getCode().toString());
		return root;
	}

	private boolean modified;

	/**
	 * 哈夫曼编码
	 * 
	 * @param list
	 * @return
	 */
	private Node haff(ArrayList<Node> list) {

		if (list.size() == 1) {
			Node node = list.get(0);
			if (!modified)
				node.setCode(new StringBuilder("0"));
			return node;
		}
		modified = true;
		list.sort(Comparator.comparing(Node::getWeight));
		// list.stream().map(Node::getWeight).forEach(System.out::println);
		// list=list.stream().sorted(Comparator.comparing(Node::getWeight)).collect(Collectors.toCollection(ArrayList::new));
		Node left = list.remove(0);
		Node right = list.remove(0);

		Node root = new Node("@", left.getWeight() + right.getWeight(), false);
		root.setLeft(left);
		root.setRight(right);
		list.add(root);

		Node realRoot = haff(list);

		left.code.append(root.code).append("0");
		right.code.append(root.code).append("1");

		if (left.getIs())
			this.code.put(left.getValue(), left.getCode().toString());
		if (right.getIs())
			this.code.put(right.getValue(), right.getCode().toString());

		return realRoot;
	}

	public void compress(String text, String path) {
		saveToFile(compress_(text), path);
	}

	private byte[] compress_(String text) {
		int size = text.length();
		this.mod = size % 8;
		int length = mod == 0 ? size / 8 : size / 8 + 1;
		byte[] bytes = new byte[length];
		byte[] every_Bits = new byte[1];
		BitSet bits;
		int i;
		for (i = 0; i < size - mod; i += 8) {
			String sub = text.substring(i, i + 8).trim();
			bits = BitSet.valueOf(every_Bits);
			for (int j = 0; j < 8; ++j) {
				if (sub.charAt(j) == '0') {
					bits.clear(7 - j);
				} else if (sub.charAt(j) == '1') {
					bits.set(7 - j);
				}
			}
			byte[] set_Bits = bits.toByteArray();
			bytes[i / 8] = set_Bits.length == 0 ? 0 : set_Bits[0];
		}
		if (mod != 0) {
			bits = BitSet.valueOf(every_Bits);
			String sub = text.substring(i, i + mod).trim();
			for (int j = 0; i < mod; ++j) {
				if (sub.charAt(j) == '0') {
					bits.clear(mod - j - 1);
				} else if (sub.charAt(j) == '1') {
					bits.set(mod - j - 1);
				}
			}
			byte[] set_Bits = bits.toByteArray();
			bytes[i / 8] = set_Bits.length == 0 ? 0 : set_Bits[0];
		}

		return bytes;
	}
	
	public  double getCompressibility(String path_Source,String path_Compress) {
		int source_Size=0;
		try(InputStream in=Files.newInputStream(Paths.get(path_Source))){
			source_Size=in.available();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		int compress_Size = 0;
		try(InputStream in=Files.newInputStream(Paths.get(path_Compress))){
			compress_Size=in.available();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return 1.0D*compress_Size/source_Size;
	}

	private String encodeText(String text) {
		StringBuilder str = new StringBuilder();
		for (int i = 0; i < text.length(); ++i) {
			char word = text.charAt(i);
			str.append(code.get(String.valueOf(word)));
		}
		return str.toString();
	}

	// 11111111
	// 00100101&
	// 1<<1 00000010
	private void saveToFile(byte[] text, String path) {
		try (OutputStream writer = Files.newOutputStream(Paths.get(path), StandardOpenOption.CREATE)) {
			writer.write(text);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public HashMap<String, String> getCode() {
		return code;
	}

	public Node getNode() {
		return root;
	}

	/**
	 * 哈夫曼树节点
	 * 
	 * @author 李德林
	 *
	 */
	public static class Node {
		private String value;
		private StringBuilder code = new StringBuilder();
		private int weight = 0;
		private boolean is;

		private Node left;
		private Node right;

		Node(String value, int weight, boolean is) {
			this.value = value;
			this.weight = weight;
			this.is = is;
		}

		public void setCode(StringBuilder code) {
			this.code = code;
		}

		public StringBuilder getCode() {
			return code;
		}

		public int getWeight() {
			return weight;
		}

		public Node getRight() {
			return right;
		}

		public void setRight(Node right) {
			this.right = right;
		}

		public Node getLeft() {
			return left;
		}

		public void setLeft(Node left) {
			this.left = left;
		}

		public boolean getIs() {
			return is;
		}

		public String getValue() {
			return value;
		}

		@Override
		public String toString() {
			return getValue();
		}

	}

	public static void main(String[] args) {
		Haff haff = new Haff();
		haff.encode(haff.load("D:\\xx.txt", false), "D:\\ee.txt");
		// haff.encode("abc");
		// haff.getCode().entrySet().forEach(System.out::println);
		haff.compress(haff.load("D:\\ee.txt", false), "D:\\ff.huf");
		System.out.println(haff.decodeByCodeMap(haff.load("D:\\ff.huf", true)));
		System.out.println(haff.getCompressibility("D:\\xx.txt","D:\\ff.huf"));
	}

}
